//
//  Problem279.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*

 279. 完全平方数 【动态规划】【拆分整数】【数学】
 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 示例 1：
     输入：n = 12
     输出：3
     解释：12 = 4 + 4 + 4
 示例 2：
     输入：n = 13
     输出：2
     解释：13 = 4 + 9
 提示：
    1 <= n <= 104
 */

@objcMembers class Problem279: NSObject {
    func solution() {
        print(numSquares(2))
        print(numSquares(12))
        print(numSquares(13))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[n]
     2: dp[j] 表示 j 完全平方数的 最少数量
     3: dp[j] = min(1 + dp[j - 1], 1 + dp[j - 4], 1 + dp[j-9], ....)
     */
    func numSquares(_ n: Int) -> Int {
        if n == 1 {
            return n
        }
        
        var dp = Array(repeating: Int.max, count: n+1)
        dp[0] = 0
        dp[1] = 1
        
        
        return numSquaresDP(n, &dp)
    }
    
    func numSquaresDP(_ n: Int, _ dp: inout [Int]) -> Int {
        if dp[n] != Int.max {
            return dp[n]
        }
        
        let max_square_index = Int(sqrt(Double(n)))  + 1;
        for i in 1...max_square_index {
            if n - i*i >= 0 {
                dp[n] = min(dp[n], 1 + numSquaresDP(n - i*i, &dp))
            }
        }
        return dp[n]
    }
}
